package com.fang.algorithm.zuo.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author lingxiao.fang
 * @Desc todo
 * @createTime 2025/3/6 11:00
 */
public class Test04_LevelPrintTree_BFS {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value) {
            this.val = value;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        List<List<Integer>> list = levelOrder(root);
        System.out.println(list);
    }

    private static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return null;
        }
        // ans
        List<List<Integer>> ansList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 当前层的最后的节点
        TreeNode nextEnd = root;
        // 当前层最后节点
        TreeNode currEnd = root;
        List<Integer> levelList = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();
            levelList.add(curr.val);
            if (curr.left != null) {
                queue.add(curr.left);
                nextEnd = curr.left;
            }
            if (curr.right != null) {
                queue.add(curr.right);
                nextEnd = curr.right;
            }
            if (curr == currEnd) {
                ansList.add(levelList);
                currEnd = nextEnd;
                levelList = new ArrayList<>();
            }
        }
        return ansList;
    }
}
